package main

import "fmt"

/**
线索存储标志位
*/
const (
	child  = iota //存储左右孩子指针
	father        //存储前驱后继的线索
)

var preNode *node

type node struct {
	data           string
	lchild, rchild *node
	ltag, rtag     int
}

/**
创建一棵二叉树,约定用户按照前序遍历的方式输入数据
*/
func newHintTree(parent string, point string) (ht *node) {
	var data string
	fmt.Printf("please input parent %s %s data:", parent, point)
	fmt.Scanln(&data)
	if data != "" {
		ht = &node{}
		ht.data = data
		ht.ltag = child
		ht.rtag = child
		ht.lchild = newHintTree(data, "left")
		ht.rchild = newHintTree(data, "right")
	}
	return
}

/**
中序遍历线索化
*/
func (ht *node) zxbl() {
	if ht != nil {
		ht.lchild.zxbl() //递归左子树
		//结点处理
		if ht.lchild == nil {
			ht.ltag = father
			ht.lchild = preNode
		}
		if preNode.rchild == nil {
			preNode.rtag = father
			preNode.rchild = ht
		}
		preNode = ht
		ht.rchild.zxbl() //递归右子树
	}
}

func (ht *node) InOrderZxbl() {
	if ht != nil {
		p := &node{}
		p.ltag = child
		p.lchild = ht
		p.rtag = father
		p.rchild = p

		preNode = p
		ht.zxbl()
		preNode.rchild = p
		preNode.rtag = father
		p.rchild = p
		preNode = p
	}
}

/**
非递归中序输出
*/
func (ht *node) zxblN() {
	p := ht.lchild
	for p != preNode {
		for p.ltag == child {
			p = p.lchild
		}
		fmt.Printf("%s-->", p.data)
		for p.rtag == father && p.rchild != preNode {
			p = p.rchild
			fmt.Printf("%s-->", p.data)
		}
		p = p.rchild
	}
}

/**
*线索二叉树
 */
func main() {
	//输入顺序(:空格)  ABC::D::E:F::
	ht := newHintTree("root", "root")
	ht.InOrderZxbl()
	ht.zxblN()
}

/*
输出结果
please input parent root root data:A
please input parent A left data:B
please input parent B left data:C
please input parent C left data:
please input parent C right data:
please input parent B right data:D
please input parent D left data:
please input parent D right data:
please input parent A right data:E
please input parent E left data:
please input parent E right data:F
please input parent F left data:
please input parent F right data:
C-->B-->D-->A-->E-->F-->
*/
